namespace _6.图;

//图定义
//G=(V,E)   Graph = (Vertex, Edge)
//V: 顶点（数据元素）的（有穷非空）集合
//E: 边的有穷集合

//无向图：每条边都是无方向的
//有向图：每条边都是有方向的

//完全图：【任意两个顶点】都有一条边【相连】（分为有向和无向完全图）
//无向完全图：n个顶点，有【n(n-1)/2】条边
//有向完全图：n个顶点，有【n(n-1)】
//条边，任意两个顶点都有相互的指向就是需要两条不同方向的边  a->b a<-b 

//稀疏图：很少边或弧（有向图的边的别名）的图 ，需满足条件(e<nLogn)
//稠密图：有较多的边或弧的图
//网：边/弧带权的图

//邻接：有边/弧相连的两个顶点的之间的关系
//存在（vi, ji）则称vi和vj互为邻接点, 无向图不分先后
//存在 <vi,vj> 则称vi邻接到vj, vj领接于vi，有向图，vi->vj, <vj,vi>则表示 vj->vi

//关联(依附)：【边/弧】与【顶点】之间的关系
//存在（vi,vj）/ <vi,vj> ，则称该边/弧关联于vi和vj

//顶点的度：与顶点相关联的边的数目，记为TD(v)
//无向图只需看关联此顶点的边即是度
//在【有向图】中，顶点的度等于该顶点的【入度】与【出度】之和
//顶点v的【入度】是以【v为终点】的有向边的条数，记作ID(v)，指向该顶点的边
//顶点v的【出度】是以【v为始点】的有向边的条数，记作OD(v)


//当有向图中仅有1个顶点的入读为0，其余顶点入度均为1，此时为树形状
//这种图称为【有向树】


//权与网
//权：图中的边或弧具有的相关树称为权。表面从一个顶点到另一个顶点的耗费或损耗
//----例子,a1->b1需要时间为20分钟，a2,b2的距离为10km
//网：带权的图称为网

//路径：【接续的边】构成的【顶点序列】
//路径长度：路径上的边或弧的【数目（边不带权值的情况）/权值（网）】之和
//回路(环)：【第一个顶点】和【最后一个顶点】相同的【路径】
//简单路径：除路径【起点和终点】【可以相同】外，【其余顶点】【均不相同】的【路径】
//简单路径（简单环）：除路径【起点和终点】【相同】外，【其余顶点】【均不相同】的【路径】

//连通图（强连通图）
//在无（有）向图G=（V，{E}）中，对【任意两个顶点】v、u都【存在从v到u的路径】，则称G是连通图（强连通图）
//【无向图】任意两点有路径叫【连通图】，而【有向图】需考虑方向因素任意两点有路径叫【强连通图】

//子图
//设：有两个图 G=（V,{E}）G1=（V1,{E1}），若V1∈V，E1∈E，则称G1是G的子图，
//顶点或者边至都是子集，但至少有一个不完全相同，若完全相同则是同一图不能称为子图

//连通分量
//无向图G的【极大连通子图】称为G的【连通分量】
//【极大连通子图】：该子图是G连通子图，将G的任何【不在该子图的顶点】加入，子图不在是【连通】的
//强连通分量
//无向图G的【极大强连通子图】称为G的【强连通分量】
//【极大强连通子图】：该子图是G强连通子图，将G的任何【不在该子图的顶点】加入，子图不在是【强连通】的


//极小连通子图：该子图是G的【连通子图】，在该子图中【删除】【任何一条边】，该子图【不在连通】。
//生成树：包含无向图G【所有顶点】的【极小连通子图】
//生成森林：对【非连通图】，由各个【连通分量】的【生成树的集合】+++++++++
